package bookForJava.P2;

import java.util.LinkedList;
/**
 * @author 许湘扬
 * @email  547139255@qq.com
 * @detail 先序创建 各种遍历 二叉树
 */
/*
 * 先序创建、输出 二叉树
 * 先序 二叉树
 *
 * 创建参考自：http://www.cnblogs.com/llhthinker/p/4906631.html
 * 遍历参考自：http://blog.csdn.net/sjf0115/article/details/8645991
 */

public class BinaryTree<T>
{
    /*
     * 先序遍历创建二叉树
     * 返回：根节点
     */
    public TreeNode<T>  creatBinaryPre(LinkedList<T> treeData)
    {
        TreeNode<T> root=null;
        T data=treeData.removeFirst();
        if (data!=null)
        {
            root=new TreeNode<T>(data, null, null);
            root.left=creatBinaryPre(treeData);
            root.right=creatBinaryPre(treeData);
        }
        return root;
    }

    /*
 * 中序遍历创建二叉树  实现不了
 * 返回：根节点
 */
    public TreeNode<T>  creatBinaryMid(LinkedList<T> treeData)
    {
        TreeNode<T> root=null;
        return root;
    }

    /*
* 后序遍历创建二叉树
* 返回：根节点
*/
    public TreeNode<T>  creatBinaryBac(LinkedList<T> treeData)
    {
        TreeNode<T> root=null;
        T data=treeData.removeLast();
        if (data!=null)
        {
            root=new TreeNode<T>(data, null, null);
            root.right=creatBinaryBac(treeData);
            root.left=creatBinaryBac(treeData);
        }
        return root;
    }

    /*
* 按层创建二叉树
* 返回：根节点
*/
    public TreeNode<T> creatBinaryLayer(LinkedList<T> treeData) {
//        TreeNode<T> root=null;
        LinkedList<TreeNode<T>> nodeList= new LinkedList<TreeNode<T>>();
        System.out.print("treeData.size:"+treeData.size()+"\n");
        int treeDataSize = treeData.size();

        // 将一个LinkedList的值依次转换为TreeNode<T>节点
        for (int nodeIndex = 0; nodeIndex < treeDataSize; nodeIndex++) {
            nodeList.add(new TreeNode<T>(treeData.removeFirst(),null,null));
        }
        // 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树
        for (int parentIndex = 0; parentIndex < treeDataSize / 2 - 1; parentIndex++) {
            // 左孩子
            nodeList.get(parentIndex).left = nodeList.get(parentIndex * 2 + 1);
            // 右孩子
            nodeList.get(parentIndex).right = nodeList.get(parentIndex * 2 + 2);
        }
        // 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理
        int lastParentIndex = treeDataSize / 2 - 1;
        // 左孩子
        nodeList.get(lastParentIndex).left = nodeList.get(lastParentIndex * 2 + 1);
        // 右孩子,如果数组的长度为奇数才建立右孩子
        if (treeDataSize % 2 == 1) {
            nodeList.get(lastParentIndex).right = nodeList.get(lastParentIndex * 2 + 2);
        }
        System.out.print("nodeList.get(0).data:"+nodeList.get(0).getData()+"\n");

        return nodeList.get(0);
    }



    /*
     * 先序遍历二叉树（递归）
     */
    public void PrintBinaryTreePreRecur(TreeNode<T> root)
    {
        if (root!=null)
        {
            System.out.print(root.getData());
            root.left.getData();
            PrintBinaryTreePreRecur(root.left);
            PrintBinaryTreePreRecur(root.right);
        }
    }
    /*
     * 中序遍历二叉树（递归）
     */
    public void PrintBinaryTreeMidRecur(TreeNode<T> root)
    {
        if (root!=null)
        {
            PrintBinaryTreeMidRecur(root.left);
            System.out.print(root.getData());
            PrintBinaryTreeMidRecur(root.right);
        }
    }
    /*
     * 后序遍历二叉树（递归）
     */
    public void PrintBinaryTreeBacRecur(TreeNode<T> root)
    {
        if (root!=null)
        {
            PrintBinaryTreeBacRecur(root.left);
            PrintBinaryTreeBacRecur(root.right);
            System.out.print(root.getData());
        }
    }
    /*
     * 先序遍历二叉树（非递归）
     * 思路：对于任意节点T，访问这个节点并压入栈中，然后访问节点的左子树，
     *      遍历完左子树后，取出栈顶的节点T，再先序遍历T的右子树
     */
    public void PrintBinaryTreePreUnrecur(TreeNode<T> root)
    {
        TreeNode<T> p=root;//p为当前节点
        LinkedList<TreeNode> stack=new LinkedList();
        //栈不为空时，或者p不为空时循环
        while(p!=null || !stack.isEmpty())
        {
            //当前节点不为空。访问并压入栈中。并将当前节点赋值为左儿子
            if (p!=null)
            {
                stack.push(p);
                System.out.print(p.getData());
                p=p.left;
            }
            //当前节点为空：
            //  1、当p指向的左儿子时，此时栈顶元素必然是它的父节点
            //  2、当p指向的右儿子时，此时栈顶元素必然是它的爷爷节点
            //取出栈顶元素，赋值为right
            else
            {
                p=stack.pop();
                p=p.right;
            }
        }
    }
    /*
     * 中序遍历二叉树（非递归）
     *
     * 思路：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，
     *       出栈，访问T->data，再中序遍历T的右子树。
     */
    public void PrintBinaryTreeMidUnrecur(TreeNode<T> root)
    {
        TreeNode<T> p=root;//p为当前节点
        LinkedList<TreeNode> stack=new LinkedList<>();

        //栈不为空时，或者p不为空时循环
        while(p!=null || !stack.isEmpty())
        {
            //当前节点不为空。压入栈中。并将当前节点赋值为左儿子
            if (p!=null)
            {
                stack.push(p);
                p=p.left;
            }
            //当前节点为空：
            //  1、当p指向的左儿子时，此时栈顶元素必然是它的父节点
            //  2、当p指向的右儿子时，此时栈顶元素必然是它的爷爷节点
            //取出并访问栈顶元素，赋值为right
            else
            {
                p=stack.pop();
                System.out.print(p.getData());
                p=p.right;
            }
        }
    }
    /*
     * 后序遍历二叉树（非递归）
     *
     */
    public void PrintBinaryTreeBacUnrecur(TreeNode<T> root)
    {
        class NodeFlag<T>
        {
            TreeNode<T> node;
            char tag;
            public NodeFlag(TreeNode<T> node, char tag) {
                super();
                this.node = node;
                this.tag = tag;
            }
        }
        LinkedList<NodeFlag<T>> stack=new LinkedList<>();
        TreeNode<T> p=root;
        NodeFlag<T> bt;
        //栈不空或者p不空时循环
        while(p!=null || !stack.isEmpty())
        {
            //遍历左子树
            while(p!=null)
            {
                bt=new NodeFlag(p, 'L');
                stack.push(bt);
                p=p.left;
            }
            //左右子树访问完毕访问根节点
            while(!stack.isEmpty() && stack.getFirst().tag=='R')
            {
                bt=stack.pop();
                System.out.print(bt.node.getData());
            }
            //遍历右子树
            if (!stack.isEmpty())
            {
                bt=stack.peek();
                bt.tag='R';
                p=bt.node;
                p=p.right;
            }
        }
    }
    /*
     * 层次遍历二叉树（非递归）
        */
    public void PrintBinaryTreeLayerUnrecur(TreeNode<T> root)
    {
        LinkedList<TreeNode> queue=new LinkedList<>();
        TreeNode<T> p;
        queue.offer(root);
        while(!queue.isEmpty())
        {
            p=queue.removeFirst();
            System.out.print(p.getData());
            if (p.left!=null)
                queue.addLast(p.left);
            if (p.right!=null)
                queue.addLast(p.right);
        }
    }

}


class TreeNode<T>
{
    private T data;
    public TreeNode<T> left;
    public TreeNode<T> right;
    public TreeNode(T data, TreeNode<T> left, TreeNode<T> right)
    {
        this.setData(data);
        this.left = left;
        this.right = right;
    }
public T getData() {
    return data;
}public void setData(T data) {
    this.data = data;
}}